©PaperWeekly 原创 · 作者 | 苏剑林
今天我们来学习 Johnson-Lindenstrauss 引理，由于名字比较长，下面都简称“JL 引理”。
个人认为，JL 引理是每一个计算机科学的同学都必须了解的神奇结论之一，它是一个关于降维的著名的结果，它也是高维空间中众多反直觉的“维度灾难”现象的经典例子之一。可以说，JL 引理是机器学习中各种降维、Hash 等技术的理论基础，此外，在现代机器学习中，JL 引理也为我们理解、调试模型维度等相关参数提供了重要的理论支撑。
JL 引理，可以非常通俗地表达为：
通俗版 JL 引理：塞下 个向量，只需要 维空间。具体来说，JL 引理说的是，不管这 个向量原来是多少维的，我们都可以将它们降到 ，并将相对距离的误差控制在一定范围内。可以想象，这是一个非常强、非常反直觉、非常实用的结论，比如我们要做向量检索，原本的向量维度可能非常大，这样全量检索一次的成本也非常大，而 JL 引理告诉我们，可以将它们变换到 维，并且检索效果近似不变，这简直就是“天上掉馅饼”的好事！可能读者会有疑问：这么强的结论，那么对应的降维方法会不会特别复杂？答案是刚刚相反，降维过程仅仅用到随机线性投影！甚至有评价说，JL 引理是一个“证明比理解更容易的结论”，也就是说，从数学上证明它还真不算特别困难，但如何直观地理解这个反直觉的结论，反而是不那么容易的。
无独有偶，我们之前其实就介绍过两个反直觉的结果：在文章《n 维空间下两个随机向量的夹角分布》[1] 中，我们就介绍过“高维空间中任意两个向量几乎都是垂直的”，这显然与二维、三维空间的结果差距甚远；在文章《从几何视角来理解模型参数的初始化策略》[2] 中，这个结果进一步升级为“从 采样出来的 矩阵几乎是一个正交矩阵”，这更与我们一直理解的“正交性是非常苛刻的（要求转置等于逆）”有严重出入。但事实上，这两个结论不仅对，而且还跟 JL 引理直接相关。可以说，JL 引理可以看成是它们的细化和应用。所以，我们需要先用更定量的语言来刻画这两个结论，比如“几乎垂直”，那垂直的概率究竟有多少，比如“近似正交”，那误差究竟有多大。
为此，我们需要一些概率知识，其中最主要是“马尔可夫不等式”：
注意该不等式并没有对 所服从的分布有其他特别的限制，只要求随机变量的取值空间是非负的（或者等价地，负的 的概率恒为 0），证明其实非常简单：
马尔可夫不等式要求随机变量是非负的，但我们平时要处理的随机变量不一定是非负的，所以通常需要变换一下才能用。比如 不是非负的，但 是非负的，于是利用马尔可夫不等式有：
这就是“切比雪夫不等式”。
另外一个经典技巧称为“Cramér-Chernoff方法”，也是我们后面主要利用到的方法，它通过指数函数将随机变量变成非负的：对于任意 ，我们有
最左端是跟 无关的，但是最右端有一个 ，而这不等式是对于任意 都成立的。所以理论上，我们可以找到使得最右端最小的 ，以获得最高的估计精度：
现在，我们可以引入如下结果，它是 JL 引理的引理，甚至可以说，它是本文一切结论的理论基础：
单位模引理：设 是独立重复采样自 的向量， 是给定常数，那么我们有：
该引理告诉我们，当 足够大的时候， 的模长明显偏离 1 的概率是非常小的（给定 后，将以 的指数形式递减至 0），所以从 采样出来的 维向量将会非常接近单位向量。它的证明正是用到“Cramér-Chernoff方法”：首先 意味着 或 ，我们需要分别进行推导，不失一般性，先推导 的概率，根据 Cramér-Chernoff 方法，有：将 u 写成分量形式 ，其中每个分量都是独立的，分布均为 ，那么我们有：
右端的极小值在 取到，推导过程就留给读者了，然后代入得到：
其中 的证明也留给读者了。类似地，我们可以对 的概率进行推导，结果为：
其中可证 ，所以上式沿用了 的不等关系。现在两式相加，我们得到 。证毕。从“单位模引理”出发，我们可以证明“正交性引理”：
正交性引理：设 是独立重复采样自 的两个向量，是给定常数，那么我们有：
该引理告诉我们，当 足够大的时候， 的内积明显偏离 0 的概率是非常小的（给定 后，将以 的指数形式递减至 0），所以从 采样出来的两个 维向量将会非常接近正交。而结合“单位模引理”，我们就得到“从 采样出来的 矩阵几乎是一个正交矩阵”的结论了。有了“单位模引理”铺垫，它的证明不算难。我们知道如果 ，那么 ，所以根据“单位模引理”的证明，我们有：
现在我们就可以着手证明 JL 引理了，下面是它的数学表述：
数学版 JL 引理：给定 个向量 和 ，而随机矩阵 独立重复采样自 是给定常数，那么至少有 的概率，使得对于所有的 ，都成立：引理告诉我们，不管原来的向量维数 是多少，只需要 的维度，我们就可以容纳下 个向量，使得它们相对距离的偏离都不超过 。而且 JL 引理还告诉我们降维方法：只需要从 随机采样一个 的矩阵 ，然后变换 就有 的可能性达到目的。真可谓是简单实用了。证明过程也是“单位模引理”的直接应用。首先，如果 是给定的单位向量，而 独立重复采样自 ，那么 的每个分量都独立地服从 。证明也并不难，根据定义每个分量 ，由于 相互独立，所以 显然相互独立，并且由于 ，正态随机变量和的分布依然是正态分布，所以 服从正态分布，其均值为 ，其方差则为 。所以，说白了， 相当于从 独立重复采样出来的 维向量。现在代入 ，利用“单位模引理”，得到：此结果对于任意 都成立，那么遍历所有的 的组合，我们得到至少有一项 的概率不超过：
或者反过来说，对于任意 ，都成立 （等价于（16））的概率不小于：
至此，证明已经完成。
上面的 JL 引理中保持的是欧氏距离近似不变，很多时候我们检索用的是内积（比如余弦相似度）而不是欧氏距离。对此，我们有：
内积版 JL 引理：给定 个单位向量 和 ，而随机矩阵 独立重复采样自 是给定常数，那么至少有 的概率，使得对于所有的 ，都成立：
证明很简单，模仿“正交性引理”的证明即可。根据 JL 引理的证明，我们可以得到在相同的条件下，至少有 的概率同时满足对于任意 有：
动手去推过一次 JL 引理证明的同学应该能感觉到，JL 引理的结论中之所以能够出现 ，本质上是因为“单位模引理”中的概率项 是指数衰减的，而我们可以放宽这个衰减速度，让其变成多项式衰减，从而出现了 。总的来说，JL 引理告诉我们，以误差 塞下 个向量，只需要 维的空间，至于 前面的常数是多少，其实不大重要。因为事实上 JL 引理是一个非常充分的条件，实际情况中条件往往更加宽松。比如，在 JL 引理的证明中如果我们将条件改为 ，那么式（16）成立的概率就不小于：
注意 虽然小，但终究是大于 0 的，所以此时依然是存在 使得（16）成立，只不过寻找 的成本更大罢了（每次命中的概率只有 ），而如果我们只关心存在性，那么这也够了。而且，JL 引理只考虑了在随机线性投影下的降维，就已经得到 了，如果是其他更精细的降维，比如基于 SVD 的降维，是有可能得到更好的结果的（前面的系数更小）；如果非线性的降维方法也考虑进去，那么结果又能变得更优了。所以说，不需要太关心 前面的常数是多少，我们只需要知道 的量级，如果真要用到它，通常还需要根据实际情况确定前面的常数，而不是调用理论结果。
在这篇文章中，我们介绍了 Johnson–Lindenstrauss 引理（JL 引理），它是关于降维的一个重要而奇妙的结论，是高维空间的不同寻常之处的重要体现之一。它告诉我们“只需要 维空间就可以塞下 个向量”，使得原本高维空间中的检索问题可以降低到 维空间中。本文主要讨论了 JL 引理的相关理论证明细节，下一篇文章我们则尝试应用它来理解一些机器学习问题，敬请期待。[1] https://kexue.fm/archives/7076
[2] https://kexue.fm/archives/7180
感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。
📝 稿件基本要求：
• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题
• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道：
• 投稿邮箱：hr@paperweekly.site
• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿
△长按添加PaperWeekly小编
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧